////https://www.luogu.com.cn/problem/P1004
//
//#include<iostream>
//
//using namespace std;
//typedef long long ll;
//const int N = 11;
//ll x[N][N], dp[2 * N][N][N];
//int main()
//{
//	int n; cin >> n;
//	int a = 1, b ,c;
//	while (cin >> a >> b >> c, a || b || c)
//		x[a][b] = c;
//	
//	for (int s = 2; s <= 2 * n; s++)
//	{
//		for (int i1 = 1; i1 <= n; i1++)
//		{
//			if (s - i1 <= 0 || s - i1 > n) continue;
//			for (int i2 = 1; i2 <= n; i2++)
//			{
//				if (s - i2 <= 0 || s - i2 > n) continue;
//				int j1 = s - i1, j2 = s - i2;
//				ll& t = dp[s][i1][i2];
//				t = max(t, dp[s - 1][i1 - 1][i2 - 1]);
//				t = max(t, dp[s - 1][i1 - 1][i2]);
//				t = max(t, dp[s - 1][i1][i2 - 1]);
//				t = max(t, dp[s - 1][i1][i2]);
//				if (i1 == i2) t += x[i1][j1];
//				else t += x[i1][j1] + x[i2][j2];
//			}
//		}
//	}
//	cout << dp[2 * n][n][n];
//	return 0;
//}